package may;

import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-28 11:36
 * @description： 今天依旧是贪心啊
 * @modified By：
 * @version:
 */
public class May28 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/car-pooling/ 拼车\
     * 首先应该要按照上车地点进行排序
     * create time: 2020-5-28 11:38
     * @params [trips, capacity]
     * @return boolean
     */
    public static boolean carPooling(int[][] trips, int capacity) {
        int number = 0;//当前车里有多少人
        Arrays.sort(trips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        Map<Integer,Integer> map = new HashMap<>();
        int j = 0;
        for (int i = 0;j<trips.length; i++) {
            if(map.get(i)!=null){//看看有没有要下车
                number-=map.get(i);
            }
            for (;j<trips.length; j++) {//要在这个位置上车的人
                if(trips[j][1]!=i){
                    break;
                }
                number+=trips[j][0];
                if(map.get(trips[j][2])!=null){
                    map.put(trips[j][2],map.get(trips[j][2])+trips[j][0]);
                }else{
                    map.put(trips[j][2],trips[j][0]);
                }
            }
            if(number>capacity){
                return false;
            }
        }
        return true;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/longest-happy-string/ 最长快乐字符串
     * create time: 2020-5-28 16:28
     * @params [a, b, c]
     * @return java.lang.String
     */
    public String longestDiverseString(int a, int b, int c) {
        MyChar[] myChars = new MyChar[]{
                new MyChar('a', a),
                new MyChar('b', b),
                new MyChar('c', c),
        };
        StringBuilder sb = new StringBuilder();

        while (true) {
            Arrays.sort(myChars);
            //先放最多的, 如果上个放的2个字符串和剩余个数最多的字符相同，则放置次多的字符

            if (sb.length() >= 2 &&
                    sb.charAt(sb.length() - 1) == myChars[2].ch &&
                    sb.charAt(sb.length() - 2) == myChars[2].ch) {
                if (myChars[1].count-- > 0) {
                    sb.append(myChars[1].ch);
                } else {
                    break;
                }

            } else {
                if (myChars[2].count-- > 0) {
                    sb.append(myChars[2].ch);
                } else {
                    break;
                }
            }

        }

        return sb.toString();
    }

    private class MyChar implements Comparable {
        char ch;
        int count;

        public MyChar(char ch, int count) {
            this.ch = ch;
            this.count = count;
        }
        @Override
        public int compareTo(Object o) {
            MyChar other = (MyChar)o;
            return this.count - other.count;
        }
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
     *  先从最小的数字开始 作为子序列的头
     * create time: 2020-5-28 16:48
     * @params [nums, k]
     * @return boolean
     */
    public static boolean isPossibleDivide(int[] nums, int k) {
        if(nums.length%k!=0){
            return false;
        }
        Arrays.sort(nums);
        int a = 1;//正在构造的子列长度
        int pre = 0 ;
        for (int i = 0; i < nums.length ; i++) {
            if(nums[i]==-1){
                continue;
            }
            pre = nums[i];
            for (int j = i+1; j<nums.length ; j++) {
                if(nums[j]==pre+1){
                    a++;
                    pre = nums[j];
                    nums[j]=-1;
                    if(a==k){
                        a = 1;
                        break;
                    }
                }
            }
            if(a!=1){
                return false;
            }
        }
        return true;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/ 使括号有效的最少添加
     * create time: 2020-5-28 17:09
     * @params [S]
     * @return int
     */
    public int minAddToMakeValid(String S) {
        int ans = 0, bal = 0;
        for (int i = 0; i < S.length(); ++i) {
            bal += S.charAt(i) == '(' ? 1 : -1;

            if (bal == -1) {
                ans++;//加上一个(回复平衡
                bal++;//为了让bal恢复0
            }
        }

        return ans + bal;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/reconstruct-a-2-row-binary-matrix/ 重构 2 行二进制矩阵
     * create time: 2020-5-28 18:18
     * @params [upper, lower, colsum]
     * @return java.util.List<java.util.List < java.lang.Integer>>
     */
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        // up记录第0行可分配的1个数，lo记录第1行可分配的1个数
        int up = upper, lo = lower, sum = 0, len = colsum.length;
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i < len; i ++){
            if(colsum[i] == 2){
                up --;
                lo --;
            }
            else if(colsum[i] == 1){
                sum++;
            }
        }
        // 如果行列元素之和不相等，或行元素之和不够分配
        if(up + lo != sum || up < 0 || lo < 0){
            return list;
        }
        List<Integer> upl = new ArrayList<>();
        List<Integer> lol = new ArrayList<>();
        for(int i = 0; i < len; i ++){
            if(colsum[i] == 2){
                upl.add(1);
                lol.add(1);
            }
            else if(colsum[i] == 0){
                upl.add(0);
                lol.add(0);
            }
            else {
                // 先分配上
                if(up-- > 0){
                    upl.add(1);
                    lol.add(0);
                }
                // 再分配下
                else {
                    lol.add(1);
                    upl.add(0);
                }
            }
        }
        list.add(upl);
        list.add(lol);
        return list;
    }

    public static void main(String[] args) {
        int[][] list ={{2,1,5},{3,3,7}};
        int[] num = {1,2,3,3,4,4,5,6};
        isPossibleDivide(num,4);
        System.out.println(carPooling(list, 4));
    }
}
